//https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8?tpId=13&tqId=587690&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
//动态规划：时间复杂度o(n2);空间复杂度o（n），辅助数组dp；
//贪心解决：时间复杂度o(n/3);空间复杂度o（1）

#include <iostream>
#include <vector>
 
using namespace std;

class Solution1 {
  public:
    int cutRope(int number) {
        //不超过3直接计算
        if (number <= 3)
            return number - 1;
        //dp[i]表示长度为i的绳子可以被剪出来的最大乘积
        vector<int> dp(number + 1, 0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        //遍历后续每一个长度
        for (int i = 5; i <= number; i++)
            //可以被分成两份
            for (int j = 1; j <= i/2; j++)
                //取最大值
                dp[i] = max(dp[i], dp[j] * dp[i - j]);
        return dp[number];
    }
};

#include <cmath>
class Solution2 {
  public:
    int cutRope(int number) {
        //不超过3直接计算
        if (number <= 3)
            return number - 1;
        int a = number/3;
        int b = number%3;
        if(b == 0) return std::pow(3, a);
        if(b == 1) return std::pow(3,a-1)*4;
        return std::pow(3,a)*2;
    }
};